# 作者:小宇
# 2025年10月23日22时22分51秒
# 1225074067@qq.com

class Node:
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class BinaryTree:
    def __init__(self):
        self.root = None
        self.help_queue = []

    def level_build_tree(self, node: Node):
        self.help_queue.append(node)
        if self.root is None:
            self.root = node
        else:
            if self.help_queue[0].lchild is None:
                self.help_queue[0].lchild = node
            else:
                self.help_queue[0].rchild = node
                self.help_queue.pop(0)

    def pre_order(self,current_node:Node):
        if current_node:
            print(current_node.elem,end=" ")
            self.pre_order(current_node.lchild)
            self.pre_order(current_node.rchild)

    def mid_order(self,current_node:Node):
        if current_node:
            self.mid_order(current_node.lchild)
            print(current_node.elem,end=" ")
            self.mid_order(current_node.rchild)



    def last_order(self,current_node:Node):
        if current_node:
            self.last_order(current_node.lchild)
            self.last_order(current_node.rchild)
            print(current_node.elem,end=" ")

    def level_order(self):
        help_queue = []
        help_queue.append(self.root)
        while help_queue:
            out_node:Node = help_queue.pop(0)
            print(out_node.elem,end=" ")
            if out_node.lchild:
                help_queue.append(out_node.lchild)
            if out_node.rchild:
                help_queue.append(out_node.rchild)




if __name__== '__main__':
    tree = BinaryTree()
    for i in range(1,11):
        node = Node(i)
        tree.level_build_tree(node)
    tree.pre_order(tree.root)
    print()
    tree.mid_order(tree.root)
    print()
    tree.last_order(tree.root)
    print()
    tree.level_order()